#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
private:
	struct unit {
		int first;
		int second;
		unit(int first_, int second_) :first(first_), second(second_) {

		}
	};
public:
	vector<int> partitionLabels(string S) {
		vector<unit> vec;
		vector<int>res;
		if (S.length() < 1)
			return res;
		for (int i = 0; i < 26; ++i)
			vec.emplace_back(-1, -1);
		for (int i = 0; i < S.length(); ++i) {
			int index = S[i] - 'a';
			if (vec[index].first == -1)
				vec[index].first = i;
			vec[index].second = i;
		}
		sort(vec.begin(), vec.end(), [](const unit& left, const unit& right) {
			return left.first < right.first;
			});
		unit index(-1, -1);
		for (int i = 0; i < vec.size(); ++i) {
			if (vec[i].first == -1)
				continue;
			if (index.first == -1) {
				index = vec[i];
			}
			else {
				if (index.second <= vec[i].first) {
					res.push_back(index.second - index.first + 1);
					index = vec[i];
				}
				else {
					index.second = max(index.second, vec[i].second);
				}
			}
		}
		res.push_back(index.second - index.first + 1);
		return res;
	}
};